# !/usr/bin/env python
# -*- coding:utf-8 -*-
# @FileName : land.py
# @Time     : 2024/1/28 15:40
# @Author   : Robot-Zsj
"""
description:

求每个海洋与最近的岛屿之间的距离，即每个元素0和与之最近的元素1之间的距离，类似于最短路径问题，用广度优先搜索算法解决

既然目标是找到元素1，那么试想如果以元素1位起始点，广度搜索与之相邻且还未被访问过的元素0，并更新距离，则相当于访问了所有与元素相邻的元素0。

那么与元素1不直接相邻的元素0要如何访问呢？一个元素0不与元素1直接相邻，那么它的上下左右4个方向一定都是元素0，

而且它上下左右的这些元素0可能是与元素1直接相邻的节点，因此只需要对所有与元素1直接相邻的元素0上下左右4个节点再次访问即可

由此：

元素0分为两种

1. 第一种是与元素1直接相邻，下文将简称为第1种节点
2. 第二种是不与元素1相邻，四周均为元素0，下文简称为第2种节点。

先通过对元素1进行广度优先搜索访问到所有第1中节点，然后通过广度优先搜索算法第1种节点来访问第2种节点，这样就可以得到每个海洋和与之最近的岛屿之间的距离。
"""

from collections import deque


def land(matrix):
    length = len(matrix)
    width = len(matrix[0])
    re = [[0 for _ in range(width)] for _ in range(length)]
    direction = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    queue = deque([])

    # 初始化re变量时，为了便于区分哪些节点值已经被更新过，即已经找到该节点到最近岛屿的距离，将元素1的位置修改为0，即这些节点本身就是岛屿，到最近岛屿的距离为0，并且将这些的节点入队，
    # 作为迭代过程开始的前提；将元素0的位置修改为-1，只要检测到某个节点值为-1，则说明该节点还未被访问过。
    for i in range(length):
        for j in range(width):
            if matrix[i][j] == 1:
                re[i][j] = 0
                queue.append((i, j))
            else:
                re[i][j] = -1
    while queue:
        x, y = queue.popleft()
        for d in direction:
            x1 = x + d[0]
            y1 = y + d[1]
            if 0 <= x1 < length and 0 <= y1 < width and re[x1][y1] == -1:
                re[x1][y1] = re[x][y] + 1
                queue.append((x1, y1))
    return re


MATRIX = [
    [0, 0, 0],
    [0, 1, 1],
    [0, 0, 0]
]
print(land(MATRIX))
